package chapter22;

import java.util.*;
import java.util.stream.Collectors;

public class Chapter22Main {

    public static void main(String[] args) {
        List<Node> V = new ArrayList<>();
        V.add(new Node(1));
        V.add(new Node(2));
        V.add(new Node(3));
        V.add(new Node(4));
        // 图顶点
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        // 邻接表
        Node[] G = new Node[5];
        G[1] = new Node(1);
        G[1].next = new Node(2);
        G[2] = new Node(2);
        G[2].next = new Node(3);
        G[2].next.next = new Node(4);
        G[3] = new Node(3);
        G[3].next = new Node(1);
        G[3].next.next = new Node(4);
        G[4] = new Node(4);

        // 广度遍历
//        bfs(G, G[1]);
        // 深度遍历
//        dfs(V, G);
        // 拓扑排序
//        List<Node> topo = topoDfs(V, G);
//        System.out.println(topo.stream().map(Node::getKey).collect(Collectors.toList()));
        // 强连通分量
        stronglyConnectedComponents(V, G);
    }

    public static void bfs(Node[] G, Node s) {
        s.color = GRAY;
        s.d = 0;
        s.p = null;
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(s);
        while (!queue.isEmpty()) {
            Node u = queue.poll();
            System.out.println("u->" + u.key);
            // 遍历u相邻边的v
            Node next = u;
            while (next != null) {
                Node v = G[next.key];
                if (v.color == WHILE) {
                    v.color = GRAY;
                    v.d = u.d + 1;
                    v.p = u;
                    queue.add(v);
                }
                next = next.next;
            }
            u.color = BLACK;
        }
    }

    static int time = 0;

    public static void dfs(List<Node> V, Node[] G) {
        time = 0;
        for (Node u : V) {
            if (G[u.key].color == WHILE) {
                dfsVisit(G, G[u.key]);
            }
        }
    }

    public static void dfsVisit(Node[] G, Node u) {
        time = time + 1;
        u.d = time;
        u.color = GRAY;
        // 遍历u相邻边的v
        Node next = u.next;
        while (next != null) {
            Node v = G[next.key];
            if (v.color == WHILE) {
                v.p = u;
                dfsVisit(G, v);
            }
            next = next.next;
        }
        u.color = BLACK;
        time = time + 1;
        u.f = time;
    }

    public static LinkedList<Node> topoDfs(List<Node> V, Node[] G) {
        LinkedList<Node> topo = new LinkedList<>();
        time = 0;
        for (Node u : V) {
            if (G[u.key].color == WHILE) {
                topoDfsVisit(G, G[u.key], topo);
            }
        }
        return topo;
    }

    public static void topoDfsVisit(Node[] G, Node u, LinkedList<Node> topo) {
        time = time + 1;
        u.d = time;
        u.color = GRAY;
        // 遍历u相邻边的v
        Node next = u;
        while (next != null) {
            Node v = G[next.key];
            if (v != null && v.color == WHILE) {
                v.p = u;
                topoDfsVisit(G, v, topo);
            }
            next = next.next;
        }
        u.color = BLACK;
        time = time + 1;
        u.f = time;
        topo.addFirst(u);
    }

    public static void stronglyConnectedComponents(List<Node> V, Node[] G) {
        List<Node> topo = topoDfs(V, G);
        Node[] GT = reverse(V, G);
        List<Node> VT = new ArrayList<>();
        for (Node v : topo) {
            VT.add(new Node(v.key));
        }
        topo = topoDfs(VT, GT);
        for (Node u : topo) {
            System.out.println(u);
        }
    }

    public static Node[] reverse(List<Node> V, Node[] G) {
        Node[] GT = new Node[G.length];
        for (int i = 0; i < V.size(); i++) {
            GT[i + 1] = new Node(V.get(i).key);
        }
        for (Node v : V) {
            Node tv = G[v.key];
            Node next = tv.next;
            while (next != null) {
                Node curr = GT[next.key];
                // 加到末端
                while (true) {
                    if (curr.next == null) {
                        curr.next = new Node(tv.key);
                        break;
                    }
                    curr = curr.next;
                }
                next = next.next;
            }
        }
        return GT;
    }

    public static int WHILE = 0;
    public static int GRAY = 1;
    public static int BLACK = 2;

    public static class Node {
        public int color;
        public int d;
        public Node p;
        public Node next;
        public int key;
        public int f;

        public Node(int color, int d, Node p, Node next, int key) {
            this.color = color;
            this.d = d;
            this.p = p;
            this.next = next;
            this.key = key;
        }

        public Node(int key) {
            this.color = WHILE;
            this.d = 0;
            this.p = null;
            this.next = null;
            this.key = key;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "color=" + color +
                    ", d=" + d +
                    ", p=" + p +
                    ", key=" + key +
                    ", f=" + f +
                    '}';
        }

        public int getColor() {
            return color;
        }

        public void setColor(int color) {
            this.color = color;
        }

        public int getD() {
            return d;
        }

        public void setD(int d) {
            this.d = d;
        }

        public Node getP() {
            return p;
        }

        public void setP(Node p) {
            this.p = p;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public int getF() {
            return f;
        }

        public void setF(int f) {
            this.f = f;
        }
    }
}
